def findLoopEndIdx(s, begin):
    for i in range(begin, len(s)):
        if s[i] == ']':
            return i
    return -1


def interpreter(tape):
    stack = [0]
    i = 0
    out = []
    loops = []
    while i < len(tape):
        cmd = tape[i]
        if cmd == '+':
            stack[-1] = (stack[-1]+1) % 256
            i += 1
        elif cmd == '-':
            stack[-1] = (stack[-1]-1+256) % 256
            i += 1
        elif cmd == '^':
            if len(stack):
                stack.pop()
            i += 1
        elif cmd == '!':
            stack.append(0)
            i += 1
        elif cmd == '*':
            out.append(chr(stack[-1]))
            i += 1
        elif cmd == '[':
            if stack[-1]:
                loops.append(i)
                i += 1
            else:
                i = findLoopEndIdx(tape, i)
        elif cmd == ']':
            if stack[-1]:
                i = loops[-1]
            else:
                if len(loops):
                    loops.pop()
                i += 1
        else:
            i += 1
    return ''.join(out)
